package com.github.tangmonkmeat;

import java.util.Scanner;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/8/2 上午9:29
 */
public class 密码生成器 {

    public static void main(String[] args){
        try(Scanner sc = new Scanner(System.in)){
            final int N = sc.nextInt();
            final int M = sc.nextInt();
            int[] arr = new int[N];
            int v = 1;
            while(v <= M){
                int i = sc.nextInt();
                int j = sc.nextInt();
                for(;i <= j;i++){
                    arr[i] = v;
                }
                v++;
            }
            int sum = 0;
            for(int k = 0;k < arr.length;k++){
                sum += arr[k] * k;
            }
            System.out.println(sum % 100000009);
        }
    }

}
